from collections import defaultdict
from typing import List


class Node:
    __slots__ = 'son', 'end'

    def __init__(self):
        self.son = defaultdict()
        self.end = False


class Tire():
    def __init__(self):
        self.root = Node()

    def add(self, word):
        cur = self.root
        for c in word:
            if c not in cur.son:
                cur.son[c] = Node()
            cur = cur.son[c]
        cur.end = True

    def search(self, word):
        cur = self.root
        s = ""
        for c in word:
            s += c
            # 如果c 在字典树里面 且 c为最后一个字符 返回s 去 替换当前字符
            if c in cur.son:
                cur = cur.son[c]
                if cur.end:
                    return s
            else:
                break
        return word


class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        tire = Tire()
        for word in dictionary:
            tire.add(word)
        ans = []
        s = sentence.split(" ")
        for c in s:
            ans.append(tire.search(c))
        return " ".join(ans)